package DP.背包.每样无限;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 *
 * dp int f
 * 都是 从叶子向上返，
 * 现有叶，后有上
 *
 * 和回溯 从上到下，到0r，完全不同！
 *
 * 注：
 * if 0 r0不r1
 * 因为最顶层f 最后也要 f(son)+1 ，有+1
 *
 * 先写出暴力 -> 备忘录在其基础上改写（不可能直接生写备忘录！）
 */
public class 零钱兑换322_每样无限_后序版 {
    int[] coins;
    public int coinChange(int[] coins, int amount) {
        this.coins = coins;
        return back(amount);
    }

    Map<Integer, Integer> map = new HashMap<>();
    int back(int zt){
        if(zt == 0) return 0;
        if(zt < 0) return -1;

        int curMinCount = Integer.MAX_VALUE;// 错1 res不能放外面，因为不是公用，而是每层for普简单取min
        for (int i = 0; i < coins.length; i++) {
            // int sonMin = f(zt - coins[i]);
            int sonMin = map.containsKey(zt-coins[i])? map.get(zt - coins[i]) : back(zt - coins[i]);
            map.put(zt-coins[i], sonMin);
            if(sonMin < 0) continue; // 继续遍历for，暴力全历！
            // 从叶的min 向上传导，不是自顶向下
            curMinCount = Math.min(curMinCount, sonMin+1 );
        }
        return curMinCount == Integer.MAX_VALUE ? -1 : curMinCount;
    }

    @Test
    public void test(){
        int[] coins = new int[]{1,2,5};
        int amount = 11;
        System.out.println("res"+coinChange(coins, amount));
    }
}
